package simple;

import data.TreeNode;

import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/8/6 23:18
 */
public class No235_二叉搜索树的最近公共祖先 {
    public static void main(String[] args) {
        Solution235 solution235 = new Solution235();
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);

        TreeNode treeNode = solution235.lowestCommonAncestor(root, null, null);

    }
}

class Solution235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //迭代
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode checkTree = stack.pop();
            if (checkTree.val > p.val && checkTree.val > q.val) {
                //p,q一定在当前节点左侧
                stack.push(checkTree.left);
            } else if (checkTree.val < p.val && checkTree.val < q.val) {
                //p,q一定在当前节点右侧
                stack.push(checkTree.right);
            } else {
                return checkTree;
            }
        }
        return null;
    }

}



    //public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //    //递归
    //    if (root.val > p.val && root.val > q.val) {
    //        //左侧递归
    //        return lowestCommonAncestor(root.left, p, q);
    //    } else if (root.val < p.val && root.val < q.val) {
    //        //p,q在右侧
    //        //右侧递归
    //        return lowestCommonAncestor(root.right, p, q);
    //    } else {
    //        return root;
    //    }
    //}